﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 각 아이템의 관계를 설정(Unite) 후 같은 두 요소가 같은 요소를 갖는지를 검사.
    /// </summary>
    class UnionFindTree
    {
        private int[] par;//부모
        private int[] rank;//트리의 깊이

        public UnionFindTree(int maxSize)
        {
            par = new int[maxSize];
            rank = new int[maxSize];
            Init(maxSize);
        }
        /// <summary>
        /// 초기화
        /// </summary>
        /// <param name="n"></param>
        public void Init(int n)
        {
            for (int i = 0; i < n; i++)
            {
                par[i] = i;
                rank[i] = 0;
            }
        }
        /// <summary>
        /// 루트 찾기
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public int Find(int x)
        {
            if (par[x] == x)
            {
                return x;
            }
            else
            {
                par[x] = Find(par[x]);
                return par[x];
            }
        }
        /// <summary>
        /// x, y 관계 만들기
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        public void Unite(int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if (x == y) return;

            if (rank[x] < rank[y])
            {
                par[x] = y;
            }
            else
            {
                par[y] = x;
                if (rank[x] == rank[y])
                {
                    rank[x]++;
                }
            }
        }
        /// <summary>
        /// x,y의 루트가 같은지 검사
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        public bool Same(int x, int y)
        {
            return Find(x) == Find(y);
        }
    }
}
